package algorithm.unionfind;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/5/17 16:17
 */
public class QuickFind extends AbstractUnionFind {
    public QuickFind(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // QuickFind中树的高度2，所有元素的父节点都是根节点
        return parents[v];
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        /**
         * 将所有p1集合元素的父节点都改为p2集合元素的父节点
         */
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }
}
